# 热题100 https://leetcode.cn/studyplan/top-100-liked/
# 6/100 双指针-三数之和
# leetcode第11题: https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/11/14
from leetcode import test


def threeSum(nums: list[int]) -> list[list[int]]:
    """暴力法求解, 时间超出限制"""
    nums, res = sorted(nums), {}
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    key = str([nums[i], nums[j], nums[k]])
                    if not res.get(key):
                        res[key] = [nums[i], nums[j], nums[k]]

    return list(res.values())


def threeSum_dbpnt(nums: list[int]) -> list[list[int]]:
    """使用双指针的方法
    暴力法可以看做一个三指针的方法, 双指针的方法类似, 首先对数组进行排序.
    然后固定其中一个数字nums[i]之后再使用双指针法, 如下为一个排序后的数组:
    -4   -1   -1   0   1   2
    fix   l                r
    我们首先固定第一为 nums[0] = -4, 那么nums[l] = -1, nums[r] = 2
    如果nums[0] + nums[l] + nums[r] > 0 那么就只能将r向左移动1位以减小最后的值
    如果nums[0] + nums[l] + nums[r] < 0 那么就只能将l向右移动1位已增加最后的值
    若 nums[0] + nums[l] + nums[r] == 0 那么就可以将结果添加入最后的结果集中
    我们遍历所有可能性之后, 将固定下一位数字
    -4   -1   -1   0   1   2
         fix   l           r
    该算法勉强通过时间限制
    """
    nums, res = sorted(nums), {}
    n = len(nums)
    for i in range(n):
        l, r = i + 1, n - 1
        while l < r:
            v = nums[i] + nums[l] + nums[r]
            if v == 0:
                key = str([nums[i], nums[l], nums[r]])
                if not res.get(key):
                    res[key] = [nums[i], nums[l], nums[r]]
                r -= 1
                l += 1
            elif v > 0:
                r -= 1
            else:
                l += 1
    return list(res.values())


def threeSum_opt(nums: list[int]) -> list[list[int]]:
    """使用双指针的一个优化的方法
    在双指针的方法中, 为了去重使用了mapping, 这里将增加判断而不适用mapping
    """
    n = len(nums)
    if n < 3:
        return []
    res = []
    nums.sort()
    if nums[0] == nums[-1]:
        return [[nums[0]] * 3]
    for i in range(n):
        if nums[i] == nums[i - 1] and i > 0:
            continue
        l, r = i + 1, n - 1
        while l < r:
            v = nums[i] + nums[l] + nums[r]
            if v == 0:
                res.append([nums[i], nums[l], nums[r]])
                while l < r and nums[l] == nums[l + 1]:
                    l += 1
                while l < r and nums[r] == nums[r - 1]:
                    r -= 1
                l += 1
                r -= 1
            elif v > 0:
                r -= 1
            else:
                l += 1
    return res


if __name__ == '__main__':
    inp = [{"nums": [-1, 0, 1, 2, -1, -4]},
           {"nums": [0, 0, 0, 0]},
           {"nums": [0, 1, 1]},
           {"nums": [-1, 0, 1, 2, -1, -4, -2, -3, 3, 0, 4]},
           {"nums": [0, 0, 0]}, ]
    out = [[[-1, -1, 2], [-1, 0, 1]],
           [[0, 0, 0]],
           [],
           [[-4, 0, 4], [-4, 1, 3], [-3, -1, 4], [-3, 0, 3], [-3, 1, 2], [-2, -1, 3], [-2, 0, 2], [-1, -1, 2],
            [-1, 0, 1]],
           [[0, 0, 0]]
           ]

    test.test_function(threeSum, inp, out, times=100)
    test.test_function(threeSum_dbpnt, inp, out, times=100)
    test.test_function(threeSum_opt, inp, out, times=100)
